// 岛屿的周长 ： https://leetcode-cn.com/problems/island-perimeter/

package main

import "container/list"

// 1. 找到所有的陆地
// 2. 如何确定陆地的周长？ 只要四条边，哪边挨着水，哪边就是一条边，算进去周长
// 深度优先遍历
func islandPerimeter(grid [][]int) int {
	n, m := len(grid), len(grid[0])
	var rst int
	var dfs func(x, y int)
	dir := [4][2]int{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}
	// 从初始化判重数组
	used := make([][]bool, n)
	for i := 0; i < n; i++ {
		used[i] = make([]bool, m)
	}
	// 先找到一块陆地
	root := findLand(grid)
	dfs = func(x, y int) {
		// 1. 终止条件，判断到水了，或者越界了，就终止了。
		if x < 0 || x >= n ||
			y < 0 || y >= m ||
			grid[x][y] == 0 {
			// 2. 只要越界 或者 为 0（水），就说明上一块地挨水，一边加一， 那么周长加1
			rst += 1
			return
		}
		// 3. 如果当前节点已经被计算过了，就不能再次计算了
		if used[x][y] {
			return
		}
		// 4. 当前节点一定表示陆地，标记为已处理。
		used[x][y] = true
		// 5. 循环查找下一下标进行处理
		for _, ac := range dir {
			// 注意这个坑， 我这里竟然错误的写成了 x, y := x + ac[0], y + ac[1]
			// 这相当于，每次都更改了原来 x, y 的值，导致循环计算下标出错！
			newX, newY := x + ac[0], y + ac[1]
			dfs(newX, newY)
		}
	}
	// 6. 调用dfs， 返回结果
	dfs(root[0], root[1])
	return rst
}

// 获取第一块是陆地的坐标的方法
func findLand(grid [][]int) [2]int {
	n, m := len(grid), len(grid[0])
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			if grid[i][j] == 1 {
				return [2]int{i, j}
			}
		}
	}
	return [2]int{}
}




// BFS 实现
func islandPerimeter1(grid [][]int) int {
	var rst int
	n, m := len(grid), len(grid[0])
	dir := [4][2]int{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}

	// 创建队列，添加进去第一个元素，置为已处理（2）
	d := list.New()
	root := findLand(grid)
	grid[root[0]][root[1]] = 2
	d.PushBack(root)

	for d.Len() > 0 {
		node := d.Remove(d.Front()).([2]int)
		x, y := node[0], node[1]

		for _, ac := range dir {
			// 判断条件 周长加 1
			if x + ac[0] < 0 || x + ac[0] >= n ||
				y + ac[1] < 0 || y + ac[1] >= m ||
				grid[x + ac[0]][y + ac[1]] == 0 {
				rst += 1
			} else if grid[x + ac[0]][y + ac[1]] == 1 {
				// 设置到这里，添加进队列就已经说明 准备处理了。 最开始设置到 for循环上面会出现问题！ 重复添加元素进队列
				grid[x + ac[0]][y + ac[1]] = 2
				d.PushBack([2]int{x + ac[0], y + ac[1]})
			} // 等于 2 的情况，就不用处理了
		}
	}

	return rst
}

// 获取第一块是陆地的坐标的方法
func findLand(grid [][]int) [2]int {
	n, m := len(grid), len(grid[0])
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			if grid[i][j] == 1 {
				return [2]int{i, j}
			}
		}
	}
	return [2]int{}
}



